# 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
#
#  candidates 中的每个数字在每个组合中只能使用一次。
#
#  说明：
#
#
#  所有数字（包括目标数）都是正整数。
#  解集不能包含重复的组合。
#
#
#  示例 1:
#
#  输入: candidates = [10,1,2,7,6,1,5], target = 8,
# 所求解集为:
# [
#   [1, 7],
#   [1, 2, 5],
#   [2, 6],
#   [1, 1, 6]
# ]
#
#
#  示例 2:
#
#  输入: candidates = [2,5,2,1,2], target = 5,
# 所求解集为:
# [
#   [1,2,2],
#   [5]
# ]
#  Related Topics 数组 回溯算法
#  👍 348 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


# todo 这题的去重和递增子序列很像，但是又有不同，必须搞懂区别和去重的细节 ，可以先看看 39 题
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        """
        先给数组升序排序。递归取每个数。如果遇到比结果大的情况，则无需继续往后搜索了。
        去重：
         对于 [1,2,2,2,5] , 5 的情况 会出现 [1,2,2] 的三次重复 
         1 2 2  _
         1 _ 2  2
         1 2 _  2
         
        观察一下可以发现后面两种情况是因为 取到 2 的时候，前面是有相同的数字,而且没有使用，所以
        遇到一个数字前，判断前面的数字相同且没有用过则 放弃使用当前数字，如此去重
        
        """

        candidates.sort()

        res = []
        visited = [False for _ in range(0, len(candidates))]
        """
        和 39 题的写法大致相同，唯一的区别在于这次出现了重复元素
        """

        def dfs(candidates, index, tmp, target):

            if target == 0:
                res.append(tmp[:])
            # 越界
            if index >= len(candidates):
                return

            # 这条分支已经无法满足
            if candidates[index] > target:
                return

            # 去重,此时这个数字不能取
            if index > 0 and candidates[index - 1] == candidates[index] and not visited[index - 1]:
                dfs(candidates, index + 1, tmp, target)
            else:
                visited[index] = True
                tmp.append(candidates[index])
                dfs(candidates, index + 1, tmp, target - candidates[index])
                tmp.pop()
                visited[index] = False
                dfs(candidates, index + 1, tmp, target)

        dfs(candidates, 0, [], target)
        return res
    # leetcode submit region end(Prohibit modification and deletion)


print(Solution().combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
